package Demo1;

class ListNode1 {
    int val;
    ListNode1 next = null;

    ListNode1(int val) {
        this.val = val;
    }
}
class Partition {
    //如果是比x大的，就放在前面，比x大的就放在后面
    //且顺序不可以改变
    public ListNode1 partition(ListNode1 pHead, int x) {
        // write code here
        ListNode1 cur = pHead;
        if(pHead == null) {
            return null;
        }
        //还要记录一下A和B的头节点
        ListNode1 headA = null;
        ListNode1 headB = null;
        ListNode1 listA = headA;
        ListNode1 listB = headB;

        while(cur != null) {
            if(cur.val < x) {
                if(listA == null) {
                    headA = cur;
                    listA = cur;
                } else {
                    listA.next = cur;
                    listA = listA.next;
                }
            } else {
                if(listB == null) {
                    headB = cur;
                    listB = cur;
                } else {
                    listB.next = cur;
                    listB = listB.next;
                }
            }

            cur = cur.next;
        }
        if(headA == null) {
            return headB;
        }
        if (headB == null) {
            return headA;
        }
        listA.next = headB;
        listB.next = null;
        return headA;
    }
}
public class t1 {
    public static void main(String[] args) {

    }
}
